#include <stdio.h>
#include <malloc.h>

typedef enum
{
    EH = 0,
    LH = 1,
    RH = -1	
}bh_t;


typedef enum
{
    FALSE = 0,
    TRUE = 1
}bool_t;

typedef int ElemType;

typedef struct BSTNode
{
    ElemType key;
    int bf;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;


void InOrderTraverse(BSTree root)
{
    if(NULL != root)
    {
        InOrderTraverse(root->lchild);
        printf("%d\t",root->key);
        InOrderTraverse(root->rchild);
    }
}


void PreOrderTraverse(BSTree root)
{
    if(NULL != root)
    {
        printf("%d\t",root->key);
        PreOrderTraverse(root->lchild);
        PreOrderTraverse(root->rchild);
    }
}


void R_Rotate(BSTree *p)
{
    BSTree lc=(*p)->lchild;
    (*p)->lchild=lc->rchild;
    lc->rchild=*p;
    *p=lc;
}


void L_Rotate(BSTree *p)
{
    BSTree rc=(*p)->rchild;
    (*p)->rchild=rc->lchild;
    rc->lchild=*p;
    *p=rc;
}


void LeftBalance(BSTree *T)
{
    BSTree lc=(*T)->lchild;
    BSTree rd = lc->rchild;
    switch(lc->bf)
    {
    case LH:
        (*T)->bf=lc->bf=EH;
        R_Rotate(T);
        break;
    case RH:
        switch(rd->bf)
        {
        case LH: 
            (*T)->bf=RH;
            lc->bf=EH;
            break;
        case EH:
            (*T)->bf=lc->bf=EH;
            break;
        case RH:
            (*T)->bf=EH;
            lc->bf=LH;
            break;
        }
        rd->bf=EH;
        L_Rotate(&((*T)->lchild));
        R_Rotate(T);
        break;
    }
}


void RightBalance(BSTree *T)
{
    BSTree rc=(*T)->rchild;
    BSTree ld=rc->lchild;
    switch(rc->bf)
    {
    case RH:
        (*T)->bf=rc->bf=EH;
        L_Rotate(T);
        break;
    case LH:
        switch(ld->bf)
        {
        case RH:
            (*T)->bf=LH;
            rc->bf=EH;
            break;
        case EH:
            (*T)->bf=rc->bf=EH;
            break;
        case LH:
            (*T)->bf=EH;
            rc->bf=RH;
            break;
        }
        ld->bf=EH;
        R_Rotate(&((*T)->rchild));
        L_Rotate(T);
        break;
    }
}


bool_t InsertAVL(BSTree *t,ElemType e,bool_t *taller)
{
    if(NULL == t)
        return FALSE;
    if(NULL == *t)
    {
        *t=(BSTree)malloc(sizeof(BSTNode));
        if(NULL == *t)
            return FALSE;
        (*t)->key=e;
        (*t)->lchild=(*t)->rchild=NULL;
        (*t)->bf=EH;
        *taller=TRUE;
    }
    else
    {
        if(e==(*t)->key)
        {
            *taller=FALSE;
            return FALSE;
        }
        if(e<(*t)->key)
        {
            if(FALSE == InsertAVL(&((*t)->lchild),e,taller))
                return FALSE; 
            if(*taller)
            {
                switch((*t)->bf)
                {
                case LH:
                    LeftBalance(t);
                    *taller=FALSE;
                    break;
                case EH:
                    (*t)->bf=LH;
                    *taller=TRUE;
                    break;
                case RH:
                    (*t)->bf=EH;
                    *taller=FALSE;
                    break;
                }
            }
        }
        else
        {
            if(FALSE == InsertAVL(&((*t)->rchild),e,taller))
                return FALSE; 
            if(*taller)
            {
                switch((*t)->bf)
                {
                case RH:
                    RightBalance(t);
                    *taller=FALSE;
                    break;
                case EH:
                    (*t)->bf=RH;
                    *taller=TRUE;
                    break;
                case LH:
                    (*t)->bf=EH;
                    *taller=FALSE;
                    break;
                }
            }
        }
    }
    return TRUE;
}


BSTree searchAVL(BSTree t,ElemType key)
{
    BSTree p=t;
    while(p)
    {
        if(p->key==key)
            return p;
        else if(p->key<key)
            p=p->rchild;
        else
            p=p->lchild;
    }
    return p;
}

static void destroy(BSTree *t)
{
    if(NULL != *t)
    {
        destroy(&((*t)->lchild));
        destroy(&((*t)->rchild));
        free(*t);
        *t = NULL;
    }
    return;
}
void destroyAVL(BSTree root)
{
    if(NULL != root)
    {
        destroy(&root);
    }
    return;
}

int main(int argc,char *argv[])
{
    BSTree root=NULL,r;
    bool_t taller=FALSE;
    int array[]={13,24,37,90,53};
    int i = 0;
    for(i=0;i<5;i++)
        InsertAVL(&root,array[i],&taller);
    printf("inorder traverse\n");
    InOrderTraverse(root);

    printf("\npreorder traverse\n");
    PreOrderTraverse(root);

    printf("\nsearch key\n");
    r=searchAVL(root,37);
    if(r)
    {
        printf("%d\n",r->key);
    }
    else
    {
        printf("not find!\n");
    }
    destroyAVL(root);
    root = NULL;
}
#if 0
--------------------- 
作者：IT_Linux 
来源：CSDN 
原文：https://blog.csdn.net/pngynghay/article/details/22443525 
版权声明：本文为博主原创文章，转载请附上博文链接！
#endif
